class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:  # 处理空输入
            return []
        
        digit_map = {
            "2": "abc", "3": "def", "4": "ghi",
            "5": "jkl", "6": "mno", "7": "pqrs",
            "8": "tuv", "9": "wxyz"
        }
        result = []
        n = len(digits)
        
        def backtrack(index: int, path: str):
            # 终止条件：路径长度等于数字长度
            if len(path) == n:
                result.append(path)
                return
            
            # 获取当前数字对应的字母
            current_digit = digits[index]
            letters = digit_map[current_digit]
            
            # 遍历当前数字的所有字母，递归选择
            for letter in letters:
                backtrack(index + 1, path + letter)
        
        backtrack(0, "")  # 从第一个数字开始，初始路径为空
        return result    